
package ija.model.types;

import ija.model.types.Tree.Node;
import ija.xls.notation.DeskCoordinate;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

/**
 * Implementace n-nárního stromu
 * Umožňuje procházet skrze 2 iterátory do hloubky a do šířky
 * 
 * @author Radek Necas, xnecas18
 */
public class Tree<T> implements Iterable<T> {
    
    /**
     * Výčet typů pro iterátory (do šířky, do hloubky)
     */
    public static enum IterType {
        BREADTH, DEPTH
    }
    
    private Node<T> root;
    
    
    /**
     * Konstruktor vytvoří prázdný strom
     */
    public Tree() {
        root = new Node<>(null, null);
    }
    
    /**
     * Konstruktor vytvoří strom
     * @param rootData data, která budou umístěna v kořenu stromu
     */
    public Tree(T rootData) {
        root = new Node<>(rootData, null);
    }
    
    
    /**
     * 
     * @return kořen stromu
     */
    public Node<T> getRoot() {
        return root;
    }
    
    /**
     * Metoda k otestování zda je strom prázdný
     * @return true pokud je strom prázdný, jinak false
     */
    public boolean isEmpty() {
        return root == null;
    }

    /** 
     * Metoda zkoumá zda je uvedena cesta uvnitř stromu.
     * Pokud je předána prázdná cesta je vraceno true (ta je vždy obsažena).
     * Nemusí jít o kompletní cestu od kořene k některému listu.
     * 
     * @param path testovaná cesta
     * @return true pokud ano, jinak false
     */
    public boolean isInside(List<T> path) {
        Node<T> node = root;
        boolean first = true;
        
        for(Object element: path) {
            if(first) {     // Prvni element je uvnitr korene
                if(!node.getData().equals(element)) {
                    return false;
                }
                first = false;
            }
            else {          // Ostatni elementy jsou obsazeny v potomcich
                node = node.getChild(element);
                if(node == null)
                    return false;
            }
            
        }
        
        return true;
    }
    
    /**
     * Metoda pro získání iterátoru
     *
     * @return iterátor pomocí kterého lze procházet strom do hloubky
     */
    @Override
    public Iterator<T> iterator() {
        return root.iterator();
    }
    
    /**
     * Metoda vytvoří iterátor daného typu
     * @param type typ iterátoru
     * @return iterátor pomocí kterého lze prozházet strom zadaným způsobem
     */
    public Iterator<T> iterator(IterType type) {
        return root.iterator(type);
    }
    
    
    /**
     * Metoda navrátí všechny možné cesty ve stromu
     * @return seznam seznamů s cestami
     */
    public List<LinkedList<Node<T>>> getPaths() {        
            LinkedList<LinkedList<Node<T>>> retList = new LinkedList<>();
            LinkedList<Node<T>> path = new LinkedList<>();
            root.getPath(retList, path);
            return retList;
    }
    
    /**
     * Metoda vypíše všechny možné cesty ve stromu.
     * Pomocná testovací metoda.
     */
    public void printPaths() {
        List<LinkedList<Node<T>>> paths = getPaths();
        DeskCoordinate coord;
        
        for(LinkedList<Node<T>> path: paths) {
            for(Node<T> pos: path) {
                System.out.print(pos.getData().toString() + "::");
                
            }
            System.out.println();
        }
    }
    
    
    // -------------------------------------------------------- //
    // ============== VNORENA TRIDA NODE ====================== //
    // -------------------------------------------------------- //
    
    /**
     * Uzel stromu
     * @param <T> typ dat, která budou v uzlu uložena
     */
    public static class Node<T> implements Iterable<T> {
        private T data;
        private Node<T> parrent;
        private List<Node<T>> children;
        
        
        /**
         * Konstruktor vytvoří nový uzel
         * 
         * @param data data která budou v uzlu uložena
         * @param parrent odkaz na rodiče
         */
        public Node(T data, Node<T> parrent) {
            this.data = data;
            children = new ArrayList<>();
            this.parrent = parrent;
        }
        
        
        /**
         * Metoda pro nastavení dat do uzlu
         * 
         * @param newData data, která se do uzlu uloží.
         */
        public void setData(T newData) {
            this.data = newData;
        }
        
        /**
         * Metoda pro přidání potomka do uzlu.
         * @param data data, která budou uložena do potomka.
         */
        public void addChild(T data) {
            children.add(new Node(data, this));
        }
        
        /**
         * Metoda pro přidání seznamu potomků do uzlu.
         * @param dataOfChildren seznam s potomky.
        */
        public void addChildren(List<T> dataOfChildren) {
            for (Iterator<T> it = dataOfChildren.iterator(); it.hasNext();) {
                T d = it.next();
                addChild(d);
            }
        }
        
        /**
         * Odstraní potomka.
         * @param index index potomka.
         */
        public void removeChild(int index) {
            if(index > 0 && index < children.size()) {
                children.remove(index);
            }
        }
        
        /**
         * Odstraní všechny potomky.
         */
        public void clearChildren() {
            children.clear();
        }
        
        
        /**
         * Odstraní data z uzlu.
         * @return 
         */
        public T getData() {
            return this.data;
        }
        
        /**
         * Vratí všechny potomky.
         * @return seznam všech potomků uzlu.
         */
        public List<Node<T>> getChildren() {
            return children;
        }
        
        /**
         * Slouží k získání specifikovaného potomka.
         * @param index index potomka
         * @return žádaný potomek (celý uzel) nebo null pokud je index mimo meze seznamu.
         */
        public Node<T> getChild(int index) {
            if(index >= 0 && index < children.size()) {
                return children.get(index);
            }
            
            return null;
        }
        
        /**
         * Metoda pro získání potomka na základě jeho dat.
         * @param childData data, která musí hledaný potomek obsahovat.
         * @return žádaný potomek (celý uzel) nebo null pokud není nalezen.
         */
        public Node<T> getChild(Object childData) {
            for(Node<T> child: children) {
                if(child.data.equals(childData)) {
                    return child;
                }
            }
            
            return null;
        }
        
        /**
         * Vrací prvního potomka
         * @return prvně vložený potomek nebo null pokud takový není.
         */
        public Node<T> getFirstChild() {
            if(children.size() > 0) {
                return children.get(0);
            }
            
            return null;
        }
        
        /**
         * Vrátí posledního potomka.
         * @return posledně přidaný potomek nebo null, pokud takový není.
         */
        public Node<T> getLastChild() {
            if(children.size() > 0) {
                return children.get(children.size() - 1);
            }
            
            return null;
        }
        
        
        /**
         * Navrátí výchozí iterátor (do hloubky).
         * @return iterátor, kterým lze procházet stromem do hloubky.
         */
        @Override
        public Iterator<T> iterator() {
            return new TreeIterator(this, IterType.DEPTH);
        }
        
        /**
         * Navrátí iterátor daného typu
         * @param type typ iterátoru
         * @return iterátor, kterým lze procházet stromem zadaným způsobem.
         */
        public Iterator<T> iterator(IterType type) {
            return new TreeIterator(this, type);
        }
        
        
        /**
         * Vrátí všechny možné cesty v seznamu.
         * Rekurzivní funkce.
         * 
         * @param retList seznam seznamů, do kterého budou cesty uloženy
         * @param pathQueue fronta do které se průběžně ukládá cesta
         */
        public void getPath(List<LinkedList<Node<T>>> retList, LinkedList<Node<T>> pathQueue) {
            pathQueue.add(this);
            for(Node<T> child: children) {
                child.getPath(retList, pathQueue);
            }
            retList.add(new LinkedList<>(pathQueue));
            pathQueue.pollLast();
        }
        
        
        /**
         * Metoda naplní frontu uzlu pro průchod do hloubky.
         * Rekurzivní metoda.
         * 
         * @param queue fronta do které se ukládají uzly
         */
        private void fillDepthDescendents(LinkedList<Node<T>> queue) {
            for(Node<T> child: children) {
                child.fillDepthDescendents(queue);
            }
            queue.add(this);
        }

        /**
         * Metoda naplní frontu uzlů pro průchod do šířky.
         * Rekurzivní metoda
         * 
         * @param queue fronta do které se ukládají uzly.
         */
        private void fillBreadthDescendents(LinkedList<Node<T>> queue) {
            if(queue.isEmpty()) {
                queue.add(this);
            }
            
            for(Node<T> child: children) {
                queue.add(child);
            }
            
            for(Node<T> child: children) {
                child.fillBreadthDescendents(queue);
            }
            
        }

    }
 
    
    // -------------------------------------------------------- //
    // ======== VNORENA TRIDA DEPTHITERATOR =================== //
    // -------------------------------------------------------- //
    
    
    /**
     * Vnořené třída reprezentuje iterátor, pomocí kterého lze procházet strom.
     * @param <T> typ dat, která jsou uložena ve stromu
     */
    public static class TreeIterator<T> implements Iterator<T> {

        LinkedList<Node<T>> queue;
        
        /**
         * Konstruktor vytvoří iterátor daného typu startující od zadaného uzlu.
         * @param start startovní uzel pro iterátor.
         * @param type typ iterátoru
         */
        public TreeIterator(Node start, IterType type) {
            queue = new LinkedList<>();
            
            if(type == IterType.DEPTH) {
                start.fillDepthDescendents(queue);
            }
            else if(type == IterType.BREADTH) {
                start.fillBreadthDescendents(queue);
            }
            
        }
        
        
        @Override
        public boolean hasNext() {
            return !queue.isEmpty();
        }

        
        @Override
        public T next() {
            return queue.poll().getData();
        }
        
        /**
         * Není prozatím implementovaná.
         */
        @Override
        public void remove() {
            throw new UnsupportedOperationException("Not supported yet.");
        }
        
    }
}
